package com.leetcode.专项突破.链表;

/**
 * @author 覃国强
 * @date 2022-03-22 20:03
 */
public class 单链表 {


  static
  class MyLinkedList {

    Node head;
    Node tail;
    int size;

    public MyLinkedList() {
      head = new Node();
      tail = head;
      size = 0;
    }

    public int get(int index) {
      if (index < 0 || index >= size) {
        return -1;
      }
      Node node = head.next;
      while (index > 0) {
        node = node.next;
        --index;
      }
      return node.value;
    }

    public void addAtHead(int val) {
      Node node = new Node(val);
      node.next = head.next;
      head.next = node;
      if (tail == head) {
        tail = node;
      }
      ++size;
    }

    public void addAtTail(int val) {
      Node node = new Node(val);
      tail.next = node;
      tail = node;
      ++size;
    }

    public void addAtIndex(int index, int val) {
      if (index == 0) {
        addAtHead(val);
      } else if (index == size) {
        addAtTail(val);
      } else if (index > 0 && index < size) {
        Node prev = head;
        while (index > 0) {
          prev = prev.next;
          --index;
        }
        Node node = new Node(val);
        node.next = prev.next;
        prev.next = node;
        ++size;
      }
    }

    public void deleteAtIndex(int index) {
      if (index >= 0 && index < size) {
        Node prev = head;
        while (index > 0) {
          prev = prev.next;
          --index;
        }
        Node deleteNode = prev.next;
        prev.next = deleteNode.next;
        if (tail == deleteNode) {
          tail = prev;
        }
        --size;
      }
    }

    static class Node {
      int value;
      Node next;

      Node() {
      }

      Node(int value) {
        this.value = value;
      }
    }

  }

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

}
